Facebook的新闻动态是如何设计的？
在互联网增长速度趋于稳定的今天，许多大厂已将面试重心从八股文转向场景题，也就是系统设计，强调应聘者在实际工作环境中的解决问题能力。这就是我推出的系统设计系列的初衷，专注于系统设计的深度学习和面试技巧。在这个系列中，提供大量真实的系统设计场景题，以及高效的解决方案。无论您是初学者还是资深从业者，都能在这里得到宝贵的知识和经验。点击关注
让我们设计Facebook的新闻动态，它将包含用户关注的所有人和页面的帖子、照片、视频和状态更新。
类似的服务：Twitter新闻动态，Instagram新闻动态，Quora新闻动态难度
级别：困难
1. 什么是Facebook的新闻动态？
新闻动态是Facebook主页中间不断更新的故事列表。它包括来自用户在Facebook上关注的人、页面和小组的状态更新、照片、视频、链接、应用活动和'赞'。换句话说，它是一个完整的可滚动版的你的朋友和你的生活故事的汇编，包括照片、视频、地点、状态更新和其他活动。
对于你设计的任何社交媒体网站 - Twitter、Instagram或Facebook - 你都需要一些新闻动态系统来展示朋友和关注者的更新。
2. 系统的需求和目标
让我们为Facebook设计一个新闻动态，有以下需求：
功能需求：
1. 新闻动态将根据用户关注的人、页面和小组的帖子生成。
2. 用户可能有很多朋友，关注很多页面/小组。
3. 新闻动态可能包含图片、视频或者只是文字。
4. 我们的服务应该支持在新帖子到达时将其添加到所有活跃用户的新闻动态中。
非功能需求：
1. 我们的系统应该能够实时生成任何用户的新闻动态 - 用户看到的最大延迟应为2秒。
2. 假设新的新闻动态请求进来，一个帖子不应该花费超过5秒才能到达用户的动态。
3. 容量估计和约束
假设平均每个用户有300个朋友，关注200个页面。
流量估计：假设每天有300M活跃用户，每个用户每天平均查看他们的时间线五次。这将每天产生15亿的新闻动态请求，或大约每秒17500个请求。
存储估计：平均来说，我们假设我们需要在每个用户的新闻动态中有大约500个帖子，我们想要在内存中保持快速获取。让我们也假设平均每个帖子的大小为1KB。这意味着我们需要为每个用户存储大约500KB的数据。为所有活跃用户存储所有这些数据，我们需要150TB的内存。如果一台服务器可以容纳100GB，我们大约需要1500台机器来为所有活跃用户保持最热门的500个帖子在内存中。
4. 系统API
💡 一旦我们确定了需求，定义系统API总是一个好主意。这应该明确地表明系统的期望。
我们可以有SOAP或REST API来暴露我们的服务的功能。以下是获取新闻动态的API的定义：
参数：api_dev_key（字符串）：注册的API开发者密钥，可以用于根据用户分配的配额进行限流等操作。user_id（数字）：系统将为其生成新闻动态的用户的ID。since_id（数字）：可选；返回ID高于（即，比）指定ID更新的结果。count（数字）：可选；指定要尝试检索的动态项数，每个不同的请求最多200个。max_id（数字）：可选；返回ID小于（即，比）或等于指定ID的结果。exclude_replies（布尔值）：可选；这个参数将阻止回复出现在返回的时间线中。
返回：（JSON）返回一个包含动态项列表的JSON对象。
5. 数据库设计
有三个主要的对象：用户(User)，实体(Entity，例如：页面、群组等)和动态项(FeedItem或帖子)。以下是这些实体之间关系的一些观察：
• 用户可以关注其他实体，也可以和其他用户成为朋友。
• 用户和实体都可以发布包含文本、图片或视频的动态项。
• 每个动态项都会有一个用户ID，指向创建它的用户。为了简化，让我们假设只有用户可以创建动态项，尽管在Facebook上，页面也可以发布动态项。
• 每个动态项可以选择性地有一个实体ID，指向创建该帖子的页面或群组。
如果我们使用关系型数据库，我们需要模型两种关系：用户-实体关系和动态项-媒体关系。由于每个用户可以和许多人成为朋友，也可以关注很多实体，我们可以在一个单独的表格中存储这种关系。"UserFollow"中的"Type"列标识被关注的实体是用户还是实体。类似地，我们可以为FeedMedia关系有一个表。
6. 高层次系统设计
从高层次上看，这个问题可以分为两部分：
动态生成：新闻动态是由用户关注的用户和实体(页面和群组)的帖子（或动态项）生成的。所以，每当我们的系统收到一个为用户(比如说Jane)生成动态的请求时，我们将执行以下步骤：
1. 检索Jane关注的所有用户和实体的ID。
2. 为这些ID检索最新的、最热门的和相关的帖子。这些是我们可以在Jane的新闻动态中展示的潜在帖子。
3. 根据这些帖子与Jane的相关性对它们进行排名。这代表了Jane的当前动态。
4. 将这个动态存储在缓存中，并返回顶部帖子（比如说20个）以渲染在Jane的动态上。
5. 在前端，当Jane到达她当前动态的末尾时，她可以从服务器获取下一个20个帖子，以此类推。
值得注意的一点是，我们一次生成动态，并将其存储在缓存中。那么Jane关注的人发出的新帖子怎么办呢？如果Jane在线，我们应该有一种机制将这些新帖子排名并添加到她的动态中。我们可以定期（比如说每五分钟）执行上述步骤，将新的帖子排名并添加到她的动态中。然后，Jane可以得到通知，她的动态中有新的项目可以获取。
动态发布：每当Jane加载她的新闻动态页面时，她必须从服务器请求并拉取动态项。当她到达当前动态的末尾时，她可以从服务器获取更多的数据。对于新的项目，服务器可以通知Jane然后她可以拉取，或者服务器可以推送这些新帖子。我们稍后会详细讨论这些选项。
从高层次上看，我们的新闻动态服务需要以下组件：
1. 网络服务器：保持与用户的连接。这个连接将被用来在用户和服务器之间传输数据。
2. 应用服务器：执行将新帖子存储在数据库服务器中的工作流。我们还需要一些应用服务器来检索和推送新闻动态到终端用户。
3. 元数据数据库和缓存：存储有关用户、页面和群组的元数据。
4. 帖子数据库和缓存：存储有关帖子及其内容的元数据。
5. 视频和照片存储，以及缓存：Blob存储，用于存储帖子中包含的所有媒体。
6. 新闻动态生成服务：收集和排名用户的所有相关帖子，生成新闻动态并存储在缓存中。这个服务也会接收实时更新，并将这些新的动态项添加到任何用户的时间线中。
7. 动态通知服务：通知用户他们的新闻动态中有新的项目可用。
下面是我们系统的高层次架构图。用户B和C正在关注用户A。
7. 细节组件设计
让我们详细讨论系统的不同组件。
a. 动态生成
考虑一个简单的例子，新闻动态生成服务从Jane关注的所有用户和实体中获取最新的帖子；查询可能像这样：
这种用于动态生成服务的设计存在以下问题：
1. 对于拥有很多朋友/关注的用户来说，我们必须对大量的帖子进行排序/合并/排名，这会非常慢。
2. 我们在用户加载他们的页面时生成时间线。这会相当慢，延迟很高。
3. 对于实时更新，每次状态更新都会导致所有关注者的动态更新。这可能会导致我们的新闻动态生成服务的积压任务数量增加。
4. 对于实时更新，服务器向用户推送（或通知）新的帖子可能会导致负载过重，尤其是对于拥有大量关注者的人或页面。为了提高效率，我们可以预先生成时间线并将其存储在内存中。
新闻动态的离线生成：我们可以有专门的服务器持续生成用户的新闻动态并将其存储在内存中。因此，无论何时用户请求获取他们动态的新帖子，我们都可以直接从预先生成的存储位置提供。使用这种方案，用户的新闻动态不是在加载时编译的，而是定期生成的，并在用户请求时返回给他们。
每当这些服务器需要为用户生成动态时，他们首先查询上次为该用户生成动态的时间。然后，从那个时间点开始生成新的动态数据。我们可以将这些数据存储在哈希表中，其中“键”是UserID，“值”是这样的结构体：
我们可以在类似LinkedHashMap或TreeMap的数据结构中存储FeedItemIDs，这不仅可以让我们跳到任何动态项，而且还可以轻松地遍历地图。每当用户想要获取更多的动态项时，他们可以发送他们在新闻动态中当前看到的最后一个FeedItemID，然后我们可以在我们的哈希图中跳到那个FeedItemID，然后从那里返回下一批/页的动态项。
我们应该为用户的动态存储多少个动态项在内存中呢？ 初始阶段，我们可以决定每个用户存储500个动态项，但这个数字可以根据使用模式在后期进行调整。例如，如果我们假设一个用户的动态页面有20个帖子，并且大多数用户从未浏览过他们的动态的十页以上，我们可以决定每个用户只存储200个帖子。对于任何想要查看更多帖子的用户（超过存储在内存中的数量），我们可以随时查询后端服务器。
我们是否应该为所有用户生成（并保持在内存中）新闻动态？会有很多用户不经常登录。这里有一些我们可以处理这个问题的方法：1) 更直接的方法可能是，使用一个基于LRU的缓存，可以从内存中删除那些长时间没有访问他们新闻动态的用户。2) 更智能的解决方案可以找出用户的登录模式以预生成他们的新闻动态，例如，用户在一天中的什么时间活跃，用户在一周中的哪些天访问他们的新闻动态等等。
现在让我们在下一节讨论一下“实时更新”问题的一些解决方案。
b. 动态发布
将帖子推送给所有关注者的过程被称为扩散。类比来说，推送方式被称为写时扩散，而拉取方式被称为加载时扩散。让我们讨论将动态数据发布给用户的不同选项。
1. “拉取”模型或加载时扩散：这种方法涉及将所有最近的动态数据保留在内存中，以便用户在需要时可以从服务器上拉取。客户端可以定期或手动拉取动态数据。当用户需要时，他们可以随时获取。这种方法可能存在的问题是a)新的数据可能直到用户发起获取请求后才会显示，b)很难找到正确的获取频率，因为大多数时候，如果没有新数据，获取请求将返回空响应，这会浪费资源。2. “推送”模型或写时广播：对于一个推送系统，一旦用户发布了一个帖子，我们可以立即将这个帖子推送给所有的关注者。优点是获取动态时，你不需要遍历你的朋友列表，然后为每一个人获取动态。它显著减少了读取操作。为了有效处理这个问题，用户必须与服务器保持一个长轮询(Long Poll)请求来接收更新。这种方法可能的问题是，当一个用户有数百万的关注者（一个名人用户）时，服务器必须向很多人推送更新。3. 混合模型：处理动态数据的另一种方法可以是使用混合方法，即，做一个写时广播和加载时广播的组合。具体来说，我们可以停止推送那些有大量关注者的用户（名人用户）的帖子，只推送那些有几百（或千）关注者的用户的数据。对于名人用户，我们可以让关注者获取更新。由于推送操作对于有大量朋友或关注者的用户来说可能非常昂贵，通过禁用他们的广播，我们可以节省大量的资源。另一个替代方案可能是，一旦用户发布了一个帖子，我们可以限制广播仅对她的在线朋友。此外，为了从两种方法中都得到好处，结合“推送通知”和“拉取服务”用户的方式是一个很好的选择。纯粹的推或拉模型较不灵活。在每次请求中，我们可以返回给客户端多少动态项？我们应该对用户在一次请求中可以获取的项目数量有一个最大限制（比如20）。但是，我们应该让客户端指定他们每次请求希望获取的动态项数量，因为用户可能希望根据设备（手机 vs. 桌面）获取不同数量的帖子。我们是否应该总是通知用户，如果有新的帖子可供他们的新闻动态？每当有新的数据可用时，用户可能会觉得有用。然而，在移动设备上，数据使用相对昂贵，可能会消耗不必要的带宽。因此，至少对于移动设备，我们可以选择不推送数据，而是让用户“下拉刷新”以获取新的帖子。
8. 动态排名
在新闻动态中对帖子进行排名的最直接方式是按照帖子的创建时间，但是现在的排名算法为了确保“重要”的帖子排名更高，正在做更多的工作。排名的高级思想首先是选择使帖子变得重要的关键“信号”，然后找出如何组合它们以计算最终的排名分数。
更具体地说，我们可以选择与任何动态项的重要性相关的特性，例如，点赞数、评论数、分享数、更新时间、帖子是否有图片/视频等，然后，可以使用这些特性计算分数。对于一个简单的排名系统来说，这通常就足够了。一个更好的排名系统可以通过不断评估我们在用户粘性、保留率、广告收入等方面是否有所进步来显著提升自身。
9. 数据分区
a. 帖子和元数据的分片 由于我们每天有大量的新帖子，而且我们的读取负载也极高，我们需要将数据分布在多台机器上，以便我们能有效地读写它。对于存储帖子及其元数据的数据库分片，我们可以采用与设计Twitter时讨论的类似设计。
b. 动态数据的分片 对于存储在内存中的动态数据，我们可以基于UserID进行分区。我们可以尝试在一台服务器上存储所有用户的数据。在存储时，我们可以将UserID传递给我们的哈希函数，该函数将用户映射到一个缓存服务器，在那里我们将存储用户的动态对象。另外，对于任何给定的用户，由于我们不期望存储超过500个动态项ID，所以我们不会遇到用户的动态数据不能存储在一台服务器上的情况。要获取用户的动态，我们只需要查询一台服务器。为了未来的发展和复制，我们必须使用一致性哈希(Consistent Hashing)。
推荐阅读
你好，我是拾叁，7年开发老司机、互联网两年外企5年。怼得过阿三老美，也被PR comments搞崩溃过。这些年我打过工，创过业，接过私活，也混过upwork。赚过钱也亏过钱。一路过来，给我最深的感受就是不管学什么，一定要不断学习。只要你能坚持下来，就很容易实现弯道超车！所以，不要问我现在干什么是否来得及。如果你还没什么方向，可以先关注我，这里会经常分享一些前沿资讯和编程知识，帮你积累弯道超车的资本。